<!DOCTYPE html>
<html lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>CLI Back-End and Front-End</title>
<link rel="stylesheet" type="text/css" href="https://gcc.gnu.org/gcc.css" />
</head>

<body>
<h1>CLI Back-End and Front-End</h1>

<h2>Table of Contents</h2>

<ul>
<li><a href="#news">Latest news</a></li>
<li><a href="#intro">Introduction</a></li>
<li><a href="#contributing">Contributing</a></li>
<li><a href="#internals">The CLI back end</a></li>
<li><a href="#frontend">The CLI front end</a></li>
<li><a href="#readings">Readings</a></li>
</ul>

<h2 id="news">Latest News</h2>

<dl>
<dt>2009-07</dt>
<dd><p>Update CLI back end to GCC 4.4, TAG added</p></dd>
</dl>

<dl>
<dt>2009-06</dt>
<dd><p>Add support for vector types (sizes 4, 8, 16 bytes) and some arithmetic
 operators (add, sub, or, and, xor).</p>
<p> Also support Mono.Simd library with flag <code>-msimd=mono</code>.</p></dd>
</dl>

<dl>
<dt>2009-04</dt>
<dd><p>Update CLI back end to GCC 4.3, TAG added</p></dd>
</dl>

<dl>
<dt>2009-03</dt>
<dd><p>Split branch in two, cli-be and cli-fe, the first contains only the modifications
for the CLI Backend, the second instead contains the changes for the CLI Frontend</p></dd>
<dd><p>Update instructions to build a toolchain, with either DotGnu based binutils
or the new ones based on Mono library Cecil</p></dd>
</dl>

<dl>
<dt>2008-09</dt>
<dd><p>First implementation of a set of new binutils based on Mono library Mono.Cecil</p></dd>
</dl>

<dl>
<dt>2008-06-13</dt>
<dd><p>Simplified build process of a CIL toolchain.
Added binutils for cil as simple wrappers on DotGnu binutils</p></dd>
<dd><p>Added implementation of libc/libm libraries on top of mscorlib
that allows most of c applications to be compiled and run on any CIL Virtual Machine</p></dd>
</dl>

<dl>
<dt>2007-07-10</dt>
<dd><p>Added CLI front end</p></dd>
</dl>

<dl>
<dt>2007-05-14</dt>
<dd><p>Roberto Costa steps down as a maintainer, replaced by
Andrea Ornstein and Erven Rohou.</p></dd>
</dl>

<dl>
<dt>2007-01-09</dt>
<dd><p>Added documentation about the back-end internal structure.</p></dd>
</dl>

<dl>
<dt>2006-09-07</dt>
<dd><p>Creation of st/cli branch.</p></dd>
</dl>

<h2 id="intro">Introduction</h2>
<p>
CLI is a framework that defines a platform independent format for
executables and a run-time environment for the execution of applications.
The framework has been been standardized by the European Computer
Manufacturers Association [1]
and by the International Organization for Standardization (ISO/IEC 23271:2006).
CLI executables are encoded in the Common Intermediate Language (CIL),
a stack-based bytecode language.
CLI framework is designed to support several programming languages
with different abstraction levels, from object-oriented managed languages
to low-level languages with no managed execution at all.
</p>
<p>
The purpose of this project is to develop a GCC back end that produces
CLI-compliant binaries.
The initial focus is on C language (more precisely, C99);
C++ is likely to be considered in the future, as well as any
other language for which there is an interest for a CLI back end.
</p>
<p>
STMicroelectronics started this project in 2006,
as part of the European funded project ACOTES.
</p>
<p>
In 2007 to explore the potential of .NET as a deployment file format, in
collaboration with <a href="https://www.hipeac.net/">HiPEAC</a>, we
developped also a CIL front end (always using GCC).
</p>

<p>
The maintainers of the branch are
<a href="mailto:andrea.ornstein@st.com">Andrea Ornstein</a> and
<a href="mailto:erven.rohou@inria.fr">Erven Rohou</a>.
</p>

<p>
The implementation currently resides in the st/cli branch.
</p>

<p>
People currently involved in the development or that had worked on it in the past are:
</p>
<p>
<a href="mailto:robsettantasei@gmail.com">Roberto Costa</a>, 
<a href="mailto:andrea.ornstein@st.com">Andrea Ornstein</a>,
<a href="mailto:erven.rohou@inria.fr">Erven Rohou</a> and 
<a href="mailto:gabriele.svelto@gmail.com">Gabriele Svelto</a>.
</p>

<h2 id="contributing">Contributing</h2>

<p>Check out <code>st/cli-be</code> branch.</p>

<p>Being this a branch, the usual maintainer rules do not apply.
The branch is being maintained by
<a href="mailto:andrea.ornstein@st.com">Andrea Ornstein</a> and
<a href="mailto:erven.rohou@inria.fr">Erven Rohou</a>. Checking-in into
the branch is free, provided that the action was coordinated with the
branch maintainer and that the usual contribution and testing rules
are followed.
</p>

<p>There is a small
<a href="https://gcc.gnu.org/svn/gcc/branches/st/README?view=markup">README
 file</a> that explains how to build and install the GCC CLI back end and
front end and the CLI binutils (both Mono based and DotGnu based) .
</p>

<h2 id="internals">The CLI back end</h2>
<p>
Unlike a typical GCC back end, the CLI backnend stops the compilation flow
at the end of the middle-end passes and, without going through any RTL
pass, it emits CIL bytecode from GIMPLE representation.
As a matter of fact, RTL is not a convenient representation to emit
CLI code, while GIMPLE is much more suited for this purpose.
</p>
<p>
CIL bytecode is much more high-level than a processor machine code.
For instance, there is no such a concept of registers or of frame
stack; instructions operate on an unbound set of local variables
(which closely match the concept of local variables) and on elements
on top of an evaluation stack.
In addition, CIL bytecode is strongly typed and it requires high-level
data type information that is not preserved across RTL.
</p>

<h3 id="mmodel">Target machine model</h3>
<p>
Like existing GCC back ends, CLI is truly seen as a target machine
and, as such, it follows GCC policy about the organization of the
back-end specific files.
</p>
<p>
Unfortunately, it is not feasible to define a single CLI target
machine. The reason is that, in dealing with languages with
unmanaged datas like C and C++, the size of pointers of the target
machine must be known at compile time.
Therefore, separate 32-bit and 64-bit CLI targets are defined,
namely <code>cil32</code> and <code>cil64</code>.
CLI binaries compiled for <code>cil32</code> are not guaranteed to
work on 64-bit machines and vice-versa.
Current work is focusing on <code>cil32</code>
target, but the differences between the two are minimal.
</p>
<p>
Being <code>cil32</code> the target machine, the machine model
description is located in files <code>config/cil32/cil32.*</code>.
This is an overview of such a description:
</p>
<ul>
  <li>The size of pointers is set to 32 (this is <code>cil32</code>
  target, it would similarly set to 64 for <code>cil64</code>).
  Natural modes for computations go up to 64 bits.</li>

  <li>Alignment rules specify that natural alignment is always
  followed (more precisely, in the absence of <code>packed</code>
  attribute).</li>

  <li>Properties exclusively needed by RTL passes are skipped.
  This is a mere consequence of the fact that the CLI back end starts
  from GIMPLE and it does not go through RTL at all.</li>

  <li>Though the CLI back end does not reach RTL passes, there is a
  minimum set of RTL-related description that must be present anyway.
  For instance, a few instruction selection patterns are mandatory,
  while others are used by some heuristics for cost estimation;
  there must be a definition of the register sets and a few peculiar
  registers have to be defined...
  As a rule of thumb, the machine model contains the simplest
  description for these properties, even if this makes little sense
  for CLI target.</li>
</ul>

<h3 id="cil_ir">The CIL intermediate representation</h3>
<p>
In our branch the traditional compilation flow of GCC has been altered to make
CIL code emission more robust and to improve the quality of the emitted code.
Instead of following the traditional compilation flow of GCC where GIMPLE code
is turned back into generic when exiting the SSA-form and then into RTL for
further processing (lower-level optimizations, instruction selection, register
allocation, scheduling and assembly emission), we remove the RTL passes and
translate generic right after the out-of-SSA phase into a specialized IR for
further processing.
</p>

<p>
Our RTL-replacement IR is loosely modeled against GIMPLE tuples, between the
two IR formats there are substantial differences but most of the philosophy
behind GIMPLE tuples is retained. We kept an eye on the gimple-tuples branch
because it will be the middle-end representation in the next release and we
wanted to design an IR which would be immediately familiar to people who worked
on GCC.
</p>

<p>
The CIL IR is closely based on the actual CIL instruction with an almost
one-to-one relationship. Ideally a single CIL IR element encapsulates all the
information and behavior of a single CIL instruction. This format allows us to
make the stack-based nature of the CIL code visible in the following passes
and greatly simplifies code emission.
</p>

<h3 id="gimple2cil">GIMPLE to CIL translation pass</h3>
<p>
GIMPLE/generic code is lowered into CIL code by descending the original trees
and expanding them one node at a time. Many GIMPLE statements can be translated
into a single CIL statement making the code generation fairly straightforward
with each node being translated and implicitly leaving its result on the stack
(except for modify statements obviously). Some statements however require
significantly more effort. Bit-field extractions and insertions are expanded
to multiple CIL statements for example.
</p>

<p>
Temporary calculation results are usually left on the stack. This is a very
natural process during expansion due to the tree-based nature of GCC IRs.
However if the order of the operands of a statement has to be change temporaries
are created as CIL does not offer any instruction for swapping the contents of
two stack slots. Duplication is possible though.
</p>

<p>
To preserve the semantics of GCC built-in functions we turn into CIL built-ins
during this phase and we provide implementations for them in the support library
which ships with our back end so that virtual machines which do not recognize
them can still execute the code correctly. Other built-ins which can be mapped
efficiently on CIL code are expanded in this phase. For example
<code>__builtin_memcpy</code> is turned into a <code>cpblk</code> instruction.
</p>

<h3 id="optimizations">CIL-specific optimizations</h3>
<p>
The GIMPLE/generic conversion phase sometimes emits some fairly poor CIL code.
The code quality actually depends much on the depth of the input trees. Very
shallow trees like those produced when compiling with <code>-O0</code> are
translated into some very poor code making use of lots of temporaries for
holding intermediate results. Under other conditions the pass creates some
naive sequences which can be easily recognized and optimized out.
</p>

<p>
For the above reasons a few optimization passes have been introduced working
directly on the CIL IR. Those passes are aware of the evaluation stack existance
and try to maximize its usage. Here's a quick run down of those passes:
</p>
<ul>
  <li>Basic blocks reordering: basic blocks are reshuffled to minimize the
  number of branches in the output code</li>
  <li>Switch expressions break up: switches can be represented in a very compact
  way in CIL but only if they are dense. Sparse switches result in very large
  code so we turn them into if-then-else expressions when it is profitable to do
  so.</li>
  <li>Missing prototypes fix-up: not really an optimization but required
  nonetheless. C89 function calls without a prototype have their types
  automatically promoted. This doesn't happen in CIL which identifies functions
  by their name and exact signature. This phase 'fixes' the unprototyped
  functions using conversion stubs to undo the automatic type promotion while
  still reflecting its behavior</li>
  <li>Removal of redundant remporaries and stack promotion: scans the code and
  locally tries to identify temporary variables and remove them promoting them
  on the evaluation stack. To implement this phase properly a full DFA should
  be done but we didn't have time for it yet. Currently this is a sort of
  glorified peephole optimizer but still manages to obtain very good results
  with little effort</li>
  <li>Redundant conversions removal: the conversion pass examines a single
  statement at a time and thus may emit redundant conversions, this pass
  analyzes the types of the variables on the stack and removes all the
  redundant conversions it can find</li>
  <li>Peephole optimizations: this pass is used to clean up simple instruction
  patterns which are emitted by the conversion pass under certain conditions
  (mostly when dealing with variable argument functions)</li>
  <li>Branch condition replacement: couples of branches (one of which being
  conditional) are altered so that they can be turned into a single branch plus
  a fall through if possible.</li>
</ul>

<h3 id="emission">Assembly emission</h3>
<p>
The last pass which emits CIL code is fairly straightforward as the intermediate
representation maps one-to-one with the CIL code. This phase however contains a
few extra functionalities which are not usually required by an assembler
emission pass.
</p>

<p>
After all the functions have been emitted this pass proceeds by emitting the
type declarations, as well as the global variables, static variables (including
function-static ones) and the string constants.
</p>

<p>
Finally the pass also supports the emission of extra custom attributes used for
representing compiler/JIT hints which cannot be expressed in plain CIL. Those
hints are emitted by using the custom attributes mechanism that the CIL standard
provides. The additional  information includes const and restrict qualifiers for
pointers and optionally the basic block frequencies as well as the branch
probabilities.
</p>

<h2 id="frontend">The CLI front end</h2>

<p>The objective of the project was to create a new GCC front end able
to take a .NET executable as input, and produce optimized native code
as output.</p>
<p>This front end, called <i>gcccil</i>, would allow us to
achieve two goals:</p>

<ul>
  <li><p>The new front end would provide a validation of a complete
  static compilation path from C to native code using CIL as
  intermediate format. This would allow using CIL as a distribution
  format for executables. In this model, the CIL image could be
  shipped to customers instead of a native executable and each
  customer could recompile said image for the native platform that he
  prefers using GCC.</p></li>

  <li><p>The front end would provide a way of producing native
  executables from CIL images.</p></li>
</ul>

<p><i>Gcccil</i> targets primarily assemblies produced by the GCC CIL
back end since this is more convenient for achieving the first of the
goals mentioned above.</p>

<h3>Implemented functionality</h3>

<p>Since the time available for the project was limited, it was not
possible to produce a complete implementation of the
standard. However, the subset implemented is enough to correctly
compile some medium sized CIL programs produced by the GCC CIL
back end.  Basically, everything required to compile assemblies
produced by the GCC CIL back end has been implemented and tested.</p>

<p>In particular, the following features have been implemented:</p>
<ul>
  <li><p>most base instructions (most of chapter 3 and some opcodes
  from chapter 4, partition II of ECMA-335),</p></li>
  <li><p>calls to static methods (direct and indirect),</p></li>
  <li><p>most CIL types (integers, reals, enums, structs, classes) can
  be parsed and used,</p></li>
  <li><p>structs with explicit layout and size,</p></li>
  <li><p>constant initializers,</p></li>
  <li><p>limited platform invoke (pInvoke) support,</p></li>
  <li><p>and other minor things like the volatile prefix, localloc,
  etc.</p></li>
</ul>

<h3>Missing functionality</h3>

<p>On the other hand, almost every feature which is not required to
compile assemblies produced by the GCC CIL back end has not been
implemented yet.</p>
<p> This includes:</p>
<ul>
  <li><p>object model related functionality (including strings and
  arrays),</p></li>
  <li><p>exceptions,</p></li>
  <li><p>garbage collection,</p></li>
  <li><p>reflection and support for .NET 2.0 generics.</p></li>
</ul>

<p>The main obstacle impeding the implementation of these features is
the lack of a runtime library (similar to <i>libgcj</i>) which is
necessary to implement virtual machine services like garbage
collection and reflection. Also, the standard class library (CORLIB)
needs to be ported for this environment.</p>

<h3>Implementation overview</h3>

<p><i>Gcccil</i> does not implement its own CLR metadata parser.
Instead, it uses <a href="https://www.mono-project.com">Mono</a>
to "parse" the input assembly. That is, Mono is used to load the assembly
and parse the metadata and types. The front end only has to parse the
actual CIL code of each method. Mono provides a comprehensive API to
allow this.</p>

<p>Once <i>gcccil</i> has loaded the assembly (or assemblies) to be
compiled, it builds GCC types for the all the types declared or
referenced in the assembly. For this, the assemblies declaring the
referenced types may need to be loaded too.</p>

<p>CIL basic types (int32, intptr, float...) are translated to their
obvious GCC equivalent. To translate classes and value types, the
GCC_RECORD_TYPE tree node is used. There is some support for class
inheritance, although it cannot be tested yet.</p>

<p>Generating types with explicit layout and size requires some
additional effort. There is already one language supported by GCC
which supports types with explicit layout (ADA), however CIL allows
the definition of some types which are not directly translatable using
the current GCC infrastructure. In particular, CIL allows to define
types with "holes". That is, types of a given size that don't have
fields defined for part of their storage (or that don't have fields at
all). However, the contents of that storage can be accessed using
pointer arithmetic and must be preserved. GCC4NET produces these kind
of types very frequently. Some optimization passes of GCC don't expect
these types, so a different representation has to be used in these
cases.</p>

<p>Once the types have been parsed, <i>gcccil</i> parses the CIL code
stream for the methods defined in the assembly in order to build GCC
GENERIC trees for them. Translating from CIL opcodes to GENERIC trees
should be straightforward once the types are built since CIL opcodes
are simple instructions that almost always have a direct translation
to GENERIC. The hardest part is using the correct type conversions to
get the correct CIL semantics in presence of all the optimizations of
GCC.</p>

<p><i>Gcccil</i> cannot compile some methods if they use some
unsupported feature. In those cases, those methods can be skipped,
allowing the user to provide a native implementation if necessary.</p>

<h2 id="readings">Readings</h2>

<dl>
<dt>[1]</dt>

<dd>
ECMA, <a href="https://www.ecma-international.org/publications-and-standards/standards/ecma-335/">
<i>Common Language Infrastructure (CLI)</i></a>, 4th edition, June 2006.
</dd>

<dt>[2]</dt>

<dd>
John Gough, <i>Compiling for the .NET Common Language Runtime (CLR)</i>,
Prentice Hall, ISBN 0-13-062296-6.
</dd>

<dt>[3]</dt>

<dd>
Serge Liden, <i>Inside Microsoft .NET IL Assembler</i>, Microsoft Press,
ISBN 073561547.
</dd>
</dl>


</body>
</html>
